package day32_other796;

import java.util.Arrays;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/10 19:31
 * @Version 1.0
 */
public class Solution {

    public double solve(int[] nums) {
        if (nums.length <= 3){
            return 0;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums[nums.length - 1] - nums[0];
        while (left <= right){
            int midden = (left + right)/ 2;
            if (possible(midden, nums)){
                right = midden - 1;
            }else {
                left = midden + 1;
            }
        }

        return (double) left / 2;
    }

    private boolean possible(int diameter, int[] nums){
        int start = nums[0], end = start + diameter;
        for (int i = 0; i < 3; i++) {
            int insertIndex = findInsertIndex(nums, end);
            if (insertIndex >= nums.length){
                return true;
            }
            start = nums[insertIndex];
            end = start + diameter;
        }

        return false;
    }

    private int findInsertIndex(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while (l <= r){
            int mid = (l + r) / 2;
            if (nums[mid] <= target){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }

        return l;
    }
}
